package com.shawn.datastructure.queue;

public class CircularDeque {

	private int[] data;
	private int size;
	private int head = 0;
	private int tail = 0;

	/**
	 * Initialize your data structure here. Set the size of the deque to be k.
	 */
	public CircularDeque(int k) {
		data = new int[k];
	}

	/**
	 * Adds an item at the front of Deque. Return true if the operation is successful.
	 */
	public boolean insertFront(int value) {
		if (size == data.length) {
			return false;
		}
		if (head != 0) {
			data[head - 1] = value;
			head = head - 1;
		} else {
			data[data.length - 1] = value;
			head = data.length - 1;
		}
		size++;
		return true;
	}

	/**
	 * Adds an item at the rear of Deque. Return true if the operation is successful.
	 */
	public boolean insertLast(int value) {
		if (size == data.length) {
			return false;
		}
		data[tail] = value;
		if (tail != data.length - 1) {
			++tail;
		} else {
			tail = 0;
		}
		++size;
		return true;
	}

	/**
	 * Deletes an item from the front of Deque. Return true if the operation is successful.
	 */
	public boolean deleteFront() {
		if (size == 0) {
			return false;
		}
		if (head != data.length - 1) {
			++head;
		} else {
			head = 0;
		}
		size--;
		return true;
	}

	/**
	 * Deletes an item from the rear of Deque. Return true if the operation is successful.
	 */
	public boolean deleteLast() {
		if (size == 0) {
			return false;
		}
		if (tail != 0) {
			--tail;
		} else {
			tail = data.length - 1;
		}
		size--;
		return true;
	}

	/**
	 * Get the front item from the deque.
	 */
	public int getFront() {
		if (size == 0) {
			return -1;
		}
		return data[head];
	}

	/**
	 * Get the last item from the deque.
	 */
	public int getRear() {
		if (size == 0) {
			return -1;
		}
		return tail == 0 ? data[data.length - 1] : data[tail - 1];
	}

	/**
	 * Checks whether the circular deque is empty or not.
	 */
	public boolean isEmpty() {
		return 0 == size;
	}

	/**
	 * Checks whether the circular deque is full or not.
	 */
	public boolean isFull() {
		return data.length == size;
	}

	public static void main(String[] args) {
		CircularDeque obj = new CircularDeque(5);

		System.out.println("obj.insertFront(1) = " + obj.insertFront(1));
		System.out.println("obj.insertFront(1) = " + obj.insertFront(2));
		System.out.println("obj.insertFront(1) = " + obj.insertFront(3));
		System.out.println("obj.insertLast(2)  = " + obj.insertLast(4));
		System.out.println("obj.insertLast(2)  = " + obj.insertLast(5));
		System.out.println("obj.getFront()     = " + obj.getFront());
		System.out.println("obj.getRear()      = " + obj.getRear());
		System.out.println("obj.deleteFront()  = " + obj.deleteFront());
		System.out.println("obj.deleteLast()   = " + obj.deleteLast());
		System.out.println("obj.getFront()     = " + obj.getFront());
		System.out.println("obj.getRear()      = " + obj.getRear());
		System.out.println("obj.isEmpty()      = " + obj.isEmpty());
		System.out.println("obj.isFull()       = " + obj.isFull());
	}
}
